Inorder Preorder Postorder

caikeal 發布于2019-08-14 17:23 / 1832人閱讀

摘要：題目鏈接參考這篇文章鏈接題目鏈接還是一樣的，用，或者保存和。題目鏈接題目鏈接按照的順序最后再一下。

Inorder Binary Tree Inorder Traversal

lc題目鏈接：https://leetcode.com/problems...

recursion：

public class Solution {
    public List inorderTraversal(TreeNode root) {
        List result = new ArrayList();
        dfs(root, result);
        return result;
    }
    
    private void dfs(TreeNode root, List result) {
        // base case
        if(root == null) return;
        dfs(root.left, result);
        result.add(root.val);
        dfs(root.right, result);
    }
}

iteration:

public class Solution {
    public List inorderTraversal(TreeNode root) {
        List result = new ArrayList();
        // stack
        Stack stack = new Stack();
        TreeNode node = root;
        while(!stack.isEmpty() || node != null) {
            while(node != null) {
                stack.push(node);
                node = node.left;
            }
            node = stack.pop();
            result.add(node.val);
            node = node.right;
        }
        return result;
    }
}

morris: 參考這篇文章
http://www.cnblogs.com/AnnieK...

public class Solution {
    public List inorderTraversal(TreeNode root) {
        /* morris: connect the node with its post if post != cur.next(cur.right == null)
         * add current when cur.left == null
         */
         List result = new ArrayList();
         TreeNode prev = null, cur = root;
         while(cur != null) {
             // reach the left most part, just add
             if(cur.left == null) {
                 result.add(cur.val);
                 // right connect to current"s post, null if finish traverse
                 cur = cur.right;
             }
             else {
                 prev = cur.left;
                 while(prev.right != null && prev.right != cur) prev = prev.right;
                 // connect prev with current: connect node with its post
                 if(prev.right == null) {
                     prev.right = cur;
                     cur = cur.left;
                 }
                 // recover the tree
                 else {
                     prev.right = null;
                     result.add(cur.val);
                     cur = cur.right;
                 }
             }
             
         }
         
         return result;
    }
}

Inorder Successor in BST

鏈接：https://leetcode.com/problems...

recursion:

public class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        // base case
        if(root == null) return null;
        // left or root
        if(p.val < root.val) {
            TreeNode left = inorderSuccessor(root.left, p);
            return left == null ? root : left;
        }
        else return inorderSuccessor(root.right, p);
    }
}

iteration:

public class Solution {
    public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
        TreeNode succ = null;
        while(root != null) {
            if(p.val < root.val) {
                succ = root;
                root = root.left;
            }
            else root = root.right;
        }
        
        return succ;
    }
}

173. Binary Search Tree Iterator

題目鏈接：https://leetcode.com/problems...
還是一樣的，iteration用stack，或者morris保存prev和cur。

public class BSTIterator {
    Stack stack;
    public BSTIterator(TreeNode root) {
        stack = new Stack();
        // get the first node
        getAllLeft(root);
    }
    
    private void getAllLeft(TreeNode node) {
        while(node != null) {
            stack.push(node);
            node = node.left;
        }
    }
    
    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return !stack.isEmpty();
    }

    /** @return the next smallest number */
    public int next() {
        if(!hasNext()) return -1;
        
        TreeNode node = stack.pop();
        if(node.right != null) getAllLeft(node.right);
        return node.val;
    }
}

Preorder Binary Tree Preorder Traversal

題目鏈接：https://leetcode.com/problems...

recursion:

public class Solution {
    public List preorderTraversal(TreeNode root) {
        // recursion
        List result = new ArrayList();
        dfs(root, result);
        return result;
    }
    
    private void dfs(TreeNode root, List result) {
        // base case
        if(root == null) return;
        
        result.add(root.val);
        dfs(root.left, result);
        dfs(root.right, result);
    }
}

iteration:

public class Solution {
    public List preorderTraversal(TreeNode root) {
        // iteration: use stack
        List result = new ArrayList();
        if(root == null)  return result;
        
        Stack stack = new Stack();
        stack.push(root);
        while(!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            result.add(cur.val);
            
            if(cur.right != null) stack.push(cur.right);
            if(cur.left != null) stack.push(cur.left);
        }
        
        return result;
    }
}

morris:

public class Solution {
    public List preorderTraversal(TreeNode root) {
        // morris: connect cur with its post in inorder
        // add as long as finding the post
        List result = new ArrayList();
        TreeNode cur = root, prev = null;
        while(cur != null) {
            // left is null, need to go to right
            if(cur.left == null) {
                result.add(cur.val);
                cur = cur.right;
            }
            else {
                prev = cur.left;
                // find the post in inorder
                while(prev.right != null && prev.right != cur) prev = prev.right;
                // connect with post and add
                if(prev.right == null) {
                    prev.right = cur;
                    result.add(cur.val);
                    cur = cur.left;
                }
                // recover the tree
                else {
                    prev.right = null;
                    cur = cur.right;
                }
            }
        }
        
        return result;
    }
}

Postorder Binary Tree Postorder Traversal

題目鏈接：https://leetcode.com/problems...

recursion:

public class Solution {
    public List postorderTraversal(TreeNode root) {
        List result = new ArrayList();
        dfs(root, result);
        return result;
    }
    
    private void dfs(TreeNode root, List result) {
        if(root == null)  return;
        
        dfs(root.left, result);
        dfs(root.right, result);
        result.add(root.val);
    }
}

iteration:

public class Solution {
    public List postorderTraversal(TreeNode root) {
        List result = new ArrayList();
        if(root == null)  return result;
        
        // right -> left -> reverse
        Stack stack = new Stack();
        stack.push(root);
        while(!stack.isEmpty()) {
            TreeNode cur = stack.pop();
            result.add(cur.val);
            if(cur.left != null) stack.push(cur.left);
            if(cur.right != null) stack.push(cur.right);
        }
        Collections.reverse(result);
        return result;
    }
}

morris: 按照root -> right -> left的順序最后再reverse一下。

public class Solution {
    public List postorderTraversal(TreeNode root) {
        List result = new ArrayList();
        // root -> right -> left
        TreeNode cur = root, prev = null;
        while(cur != null) {
            // right == null, go to left
            if(cur.right == null) {
                result.add(cur.val);
                cur = cur.left;
            }
            else {
                prev = cur.right;
                while(prev.left != null && prev.left != cur) {
                    prev = prev.left;
                }
                // connect according to inorder but right first: right->root->left
                // leftmost.left = root
                if(prev.left == null) {
                    result.add(cur.val);
                    prev.left = cur;
                    cur = cur.right;
                }
                else {
                    prev.left = null;
                    cur = cur.left;
                }
            }
        }
        
        Collections.reverse(result);
        return result;
    }
}

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/66600.html

刷題日記Day2 | 構造二叉樹

摘要：代碼實現構建二叉樹節點對應的值就是后序遍歷數組的最后一個元素在中序遍歷數組中的索引左子樹的節點個數遞歸構造左右子樹把題目的要求細化，搞清楚根節點應該做什么，然...

Hwg 2021-11-17 09:33 評論0 收藏0
Construct Binary Tree from Traversal

摘要：思路在的順序里，先，然后再左右。所以根據可以知道的。接著再分別在和的里面重復找以及左右的過程。首先的包括和，以及對應的起始和結束位置，對應的起始和結束位置。返回值為，因為每個里要一個，同時找到它的和，左右節點通過返回值獲得。同時的不需要了。 From Preorder and Inorder 思路在preorder的順序里，先root，然后再左右。所以根據preorder可以知道roo...

wenshi11019 2019-08-14 17:11 評論0 收藏0
推導二叉樹的遍歷結果

摘要：推導前序序列已知二叉樹的中序序列是，后序序列是，求前序序列。二叉樹的中序序列是按照左子樹，根，右子樹的順序排列的，根將左子樹的序列和右子樹的序列分割在左右兩邊。推導前序序列已知二叉樹的中序序列是ABCDEFG，后序序列是BDCAFGE，求前序序列。思路 showImg(https://segmentfault.com/img/bVW1es?w=723&h=431); 二叉樹的后序...

joy968 2019-08-21 17:10 評論0 收藏0
二叉樹遍歷算法收集(先序 preorder，后序 postorder，中序 inorder）循環+

摘要：指的是的位置。算法比較簡單，算法比較難想，可是原題都說了 preorder: root-left-rightinorder: left-root-rightpostorder: left-right-root order指的是root的位置。 recursive算法比較簡單，iterative算法比較難想，可是leetcode原題都說了： recursive method is tri...

沈建明 2019-08-14 15:55 評論0 收藏0
我的面試準備過程--leetcode樹

摘要：由遍歷結果反求樹分析遞歸分治，第一層需要找到相應的遍歷結果，對數組來說，問題轉化為找下標問題對前序中序遍歷結果來說前序左右中序左右因此，中序中的下標可求，為對每一層來說，左子樹的長度為，右子樹的長度為，左子樹前序為至，中序為至，可以使　由遍歷結果反求樹分析：遞歸分治，第一層需要找到相應的遍歷結果，對數組來說，問題轉化為找下標問題對前序、中序遍歷結果來說前序：[root,[左...

wenyiweb 2019-08-15 10:44 評論0 收藏0