[Vssue]二叉树的统一迭代法.md

youngyangyang04 commented 5 months ago

https://www.programmercarl.com/%E4%BA%8C%E5%8F%89%E6%A0%91%E7%9A%84%E7%BB%9F%E4%B8%80%E8%BF%AD%E4%BB%A3%E6%B3%95.html

jzlhk commented 4 months ago

优雅！好喜欢

Du1in9 commented 4 months ago

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        Stack<TreeNode> st = new Stack<>();
        if (root == null) return res;

        st.push(root);
        while (!st.empty()) {
            TreeNode node = st.peek();
            if (node != null) {
                st.pop();
                if (node.right!=null) st.push(node.right);  // 右
                if (node.left!=null) st.push(node.left);    // 左
                st.push(node);                              // 中
                st.push(null);
            } else {
                st.pop();           
                node = st.peek();  
                st.pop();
                res.add(node.val);
            }
        }
        return res;
    }
}

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        Stack<TreeNode> st = new Stack<>();
        if (root == null) return res;

        st.push(root);
        while (!st.empty()) {
            TreeNode node = st.peek();
            if (node != null) {
                st.pop();
                if (node.right!=null) st.push(node.right);  // 右
                st.push(node);                              // 中
                st.push(null);
                if (node.left!=null) st.push(node.left);    // 左
            } else {
                st.pop();           
                node = st.peek();  
                st.pop();
                res.add(node.val);
            }
        }
        return res;
    }
}

class Solution {
    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> res = new LinkedList<>();
        Stack<TreeNode> st = new Stack<>();
        if (root == null) return res;

        st.push(root);
        while (!st.empty()) {
            TreeNode node = st.peek();
            if (node != null) {
                st.pop();
                st.push(node);                              // 中
                st.push(null);
                if (node.right!=null) st.push(node.right);  // 右
                if (node.left!=null) st.push(node.left);    // 左
            } else {
                st.pop();           
                node = st.peek();  
                st.pop();
                res.add(node.val);
            }
        }
        return res;
    }
}

Ys0serious commented 3 months ago

为什么有peek/top + 两个pop这种结构，为什么不直接在最外层放一个pop就行了？有什么讲究吗？

public class Solution {
    public IList<int> InorderTraversal(TreeNode root) 
    {
        var st = new Stack<TreeNode>();
        var res = new List<int>();

        if (root == null)
        {
            return res;
        }
        st.Push(root);

        while(st.Count != 0)
        {
            var cur = st.Pop();
            if (cur != null)
            {
                if(cur.right != null)
                {
                    st.Push(cur.right);
                }
                st.Push(cur);
                st.Push(null);
                if(cur.left != null)
                {
                    st.Push(cur.left);
                }
            }
            else
            {
                cur = st.Pop();
                res.Add(cur.val);
            }
        }
        return res;

    }
}

Scenei commented 3 months ago

帅！

nonunu commented 1 month ago

都是要pop的，为什么不直接pop，不需要top或者peek吧，或者这里有什么讲究么？

lsy934127847 commented 1 month ago

统一迭代法 ,虽然结构上统一了，但是整个入栈出栈过程的推导有点复杂。

youngyangyang04 / leetcode-master-comment

[Vssue]二叉树的统一迭代法.md #80