Create 145.二叉树的后序遍历(中等).md

JavaCodeMing · JavaCodeMing · commit 50cdc24eb01a · 2020-06-27T09:22:39.000+08:00
diff --git a/Algorithm/145.二叉树的后序遍历(中等).md b/Algorithm/145.二叉树的后序遍历(中等).md
@@ -0,0 +1,87 @@
+```text
+��Ŀ: ����һ��������,��������"����"����;(�������: �������ӽڵ�,�ٱ������ӽڵ�,���Ǹ��ڵ�)
+1.�ݹ�: 
+    [1]˼·: ʹ�õݹ�ʵ�ֺ������
+        (1)ȷ���ݹ鷽���Ĳ���: ��Ҫ���еݹ�����ڵ�,���Ա���ڵ�ֵ�Ľ����
+        (2)ȷ���ݹ��߼�: �ȱ������ӽڵ�,�ٱ������ӽڵ�,�����Ӹ��ڵ�
+        (3)ȷ���ݹ鷽�����˳�����
+    [2]ʵ��: 
+        class Solution {
+            public List<Integer> postorderTraversal(TreeNode root) {
+                // �Խڵ�����п�
+                if(root == null){
+                    return new ArrayList<>();
+                }
+                List<Integer> result = new ArrayList<>();
+                dfs(root,result);
+                return result;
+            }
+            private void dfs(TreeNode node, List<Integer> result) {
+                // �ݹ�����˳�������
+                if(node == null){
+                    return;
+                }
+                // �ݹ�������ӽڵ�
+                if(node.left != null){
+                    dfs(node.left,result);
+                }
+                // �ݹ�������ӽڵ�
+                if(node.right != null){
+                    dfs(node.right,result);
+                }
+                // ���Ӹ��ڵ�ֵ
+                result.add(node.val);
+            }
+        }
+        public class TreeNode {
+            int val;
+            TreeNode left;
+            TreeNode right;
+            TreeNode(int x) { val = x; }
+        }
+    [3]���Ӷȷ���:
+        (1)ʱ�临�Ӷ�: O(N),�ݹ������ÿ���ڵ�������һ��
+        (2)�ռ临�Ӷ�: O(N),�ݹ������ÿ���ڵ�ʱ,����Ҫ��ջ(��ջ�ṹ����)
+2.ջ:
+    [1]˼·: ʹ��ջ�Ż��ݹ�ʵ�ֺ������
+        (1)��ջ��������Ҫ�����Ľڵ�,��ȥ����ջ,ÿ�α���ȡջ���ڵ�(���ڵ�)
+        (2)���ڵ�һ������������ȡ��,����ᵼ����ѭ��,��ʱ�͵ÿ��Ǹ��ڵ�ֵ������λ��
+        (3)���ں���������������,���Կ���������е�ֵ,�ٱ����������ӽڵ�,���������ӽڵ�
+    [2]ʵ��:
+        class Solution {
+            public List<Integer> postorderTraversal(TreeNode root) {
+                // �Խڵ�����п�
+                if(root == null){
+                    return new LinkedList<>();
+                }
+                LinkedList<Integer> result = new LinkedList<>();
+                // ʹ��˫�˶���ʹ��ջ
+                Deque<TreeNode> stack = new ArrayDeque<>();
+                stack.push(root);
+                while (!stack.isEmpty()){
+                    // ȡ��ջ��Ԫ��(��һ��ĸ��ڵ�)
+                    TreeNode node = stack.pop();
+                    // �������е�˳��,���ڵ�ֵҪ����͵÷����(�������ڵ����ֵ�Ÿ��ڵ�ǰ��)
+                    result.addFirst(node.val);
+                    // �������ӽڵ�
+                    if(node.left != null){
+                        stack.push(node.left);
+                    }
+                    // �������ӽڵ�
+                    if(node.right != null){
+                        stack.push(node.right);
+                    }
+                }
+                return result;
+            }
+        }
+        public class TreeNode {
+            int val;
+            TreeNode left;
+            TreeNode right;
+            TreeNode(int x) { val = x; }
+        }
+    [3]���Ӷȷ���:
+        (1)ʱ�临�Ӷ�: O(N)
+        (2)�ռ临�Ӷ�: O(N)
+```

-Original file line number
+Diff line change
@@ @@ -0,0 +1,87 @@ @@
 +```text
 +题目: 给定一个二叉树,返回它的"后序"遍历;(后序遍历: 遍历左子节点,再遍历右子节点,再是父节点)
 +1.递归:
 +    [1]思路: 使用递归实现后序遍历
 +        (1)确定递归方法的参数: 需要进行递归的树节点,用以保存节点值的结果集
 +        (2)确定递归逻辑: 先遍历左子节点,再遍历右子节点,再添加父节点
 +        (3)确定递归方法的退出条件
 +    [2]实现:
 +        class Solution {
 +            public List<Integer> postorderTraversal(TreeNode root) {
 +                // 对节点进行判空
 +                if(root == null){
 +                    return new ArrayList<>();
 +                }
 +                List<Integer> result = new ArrayList<>();
 +                dfs(root,result);
 +                return result;
 +            }
 +            private void dfs(TreeNode node, List<Integer> result) {
 +                // 递归遍历退出的条件
 +                if(node == null){
 +                    return;
 +                }
 +                // 递归遍历左子节点
 +                if(node.left != null){
 +                    dfs(node.left,result);
 +                }
 +                // 递归遍历右子节点
 +                if(node.right != null){
 +                    dfs(node.right,result);
 +                }
 +                // 添加父节点值
 +                result.add(node.val);
 +            }
 +        }
 +        public class TreeNode {
 +            int val;
 +            TreeNode left;
 +            TreeNode right;
 +            TreeNode(int x) { val = x; }
 +        }
 +    [3]复杂度分析:
 +        (1)时间复杂度: O(N),递归过程中每个节点会遍历到一次
 +        (2)空间复杂度: O(N),递归遍历到每个节点时,都需要入栈(用栈结构保存)
 +2.栈:
 +    [1]思路: 使用栈优化递归实现后序遍历
 +        (1)向栈中添加需要遍历的节点,再去遍历栈,每次遍历取栈顶节点(父节点)
 +        (2)父节点一旦遍历到必须取出,否则会导致死循环,这时就得考虑父节点值的添加位置
 +        (3)由于后续遍历是左右中,所以可以先输出中的值,再遍历添加右子节点,再添加左子节点
 +    [2]实现:
 +        class Solution {
 +            public List<Integer> postorderTraversal(TreeNode root) {
 +                // 对节点进行判空
 +                if(root == null){
 +                    return new LinkedList<>();
 +                }
 +                LinkedList<Integer> result = new LinkedList<>();
 +                // 使用双端队列使用栈
 +                Deque<TreeNode> stack = new ArrayDeque<>();
 +                stack.push(root);
 +                while (!stack.isEmpty()){
 +                    // 取出栈顶元素(上一层的父节点)
 +                    TreeNode node = stack.pop();
 +                    // 按左右中的顺序,父节点值要输出就得放最后(即其他节点遍历值放父节点前面)
 +                    result.addFirst(node.val);
 +                    // 添加左子节点
 +                    if(node.left != null){
 +                        stack.push(node.left);
 +                    }
 +                    // 添加右子节点
 +                    if(node.right != null){
 +                        stack.push(node.right);
 +                    }
 +                }
 +                return result;
 +            }
 +        }
 +        public class TreeNode {
 +            int val;
 +            TreeNode left;
 +            TreeNode right;
 +            TreeNode(int x) { val = x; }
 +        }
 +    [3]复杂度分析:
 +        (1)时间复杂度: O(N)
 +        (2)空间复杂度: O(N)
 +```