Preorder vs Postorder


  • 1
    1. let's try Preorder first. First we save left child and right child. Then we can safely flatten this node. Then left and right.
    public class Solution {
        TreeNode pre=null;
        public void flatten(TreeNode root) {
            if(root==null) return;
            TreeNode left = root.left;
            TreeNode right = root.right;
            if(pre == null) {
                pre = root;
            }else {
                pre.right = root;
                pre.left = null;
                pre = root;
            }
            flatten(left);
            flatten(right);
        }
    }
    
    
    1. Postorder is a little tricky and not easy to come up. Because the order we flatten will not change the relationship of remaining nodes we do not extra pointers.
    public class Solution {
        TreeNode pre=null;
        public void flatten(TreeNode root) {
            if(root==null) return;
            flatten(root.right);
            flatten(root.left);
            root.right=pre;
            root.left=null;
            pre = root;
        }
    }
    
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.