二叉树--后序遍历的递归和非递归(leetcode 145

非递归

思路1

用两个栈实现后序遍历的步骤:

  1. 申请一个栈stack1,将头节点压入栈中

  2. 将stack1中元素弹出,记为temp,依次将temp的左孩子,右孩子压入stack1(如果有的话

  3. 每个从stack1中弹出的元素都压入stack2

4.不断重复步骤2,3直到stack1为空停止

5.从stack2中依次弹出并打印就是后序遍历的顺序

总结:

后序遍历想要的结果是左右中。压入stack1的是中,然后弹出中,再依次向stack1压入左右,再从stack1弹出的就是右左。此时stack2中已经有中了,再压入右左。最后从stack2弹出的就是左右中。

代码:

public List<Integer> postorderTraversal(TreeNode root) {
    List<Integer> list = new LinkedList<>();
    if (root == null){return list;}
    Stack<TreeNode> stack1 = new Stack<>();
    Stack<TreeNode> stack2 = new Stack<>();
    stack1.push(root);
    TreeNode temp = root;
    while (!stack1.isEmpty()){
        temp = stack1.pop();
        stack2.push(temp);
        if (temp.left != null){
            stack1.push(temp.left);
        }
        if (temp.right != null){
            stack1.push(temp.right);
        }
    }
    while (!stack2.isEmpty()){
        list.add(stack2.pop().val);
    }
    return list;
}

思路2:用一个栈完成后序遍历

待补充


递归解法就是定义,略去不写

上一篇:ASP.NET MVC下使用文件上传


下一篇:30 Day Challenge Day 3 | Leetcode 145. Binary Tree Postorder Traversal