Tag: Binary Tree

Posted 2022-09-14Updated 2022-09-14LeetCode / Mediuma minute read (About 221 words)

1457. Pseudo-Palindromic Paths in a Binary Tree

Question

Given a binary tree where node values are digits from 1 to 9. A path in the binary tree is said to be pseudo-palindromic if at least one permutation of the node values in the path is a palindrome.

Return the number of pseudo-palindromic paths going from the root node to leaf nodes.

Solution

用数组bin[]记录一个树枝上的节点。

回溯，遇到根节点则判断数组bin[]中是否只有0个或1个奇数的数字。

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int res;
    int[] bin;
    public int pseudoPalindromicPaths (TreeNode root) {
        res = 0;
        bin = new int[10];
        backtrack(root);
        return res;
    }
    
    private void backtrack(TreeNode root){
        if(root.left == null && root.right == null){
            bin[root.val]++;
            boolean flag = false;
            for(int i = 0; i < bin.length; i++){
                if(flag && (bin[i] & 1) == 1){
                    bin[root.val]--;
                    return;
                }
                else if((bin[i] & 1) == 1) flag = true;
            }
            res++;
            bin[root.val]--;
            return;
        }
        bin[root.val]++;
        if(root.left != null) backtrack(root.left);
        if(root.right != null) backtrack(root.right);
        bin[root.val]--;
    }
}

Posted 2022-09-06Updated 2022-09-06LeetCode / Easy2 minutes read (About 277 words)

606. Construct String from Binary Tree

Question

Given the root of a binary tree, construct a string consisting of parenthesis and integers from a binary tree with the preorder traversal way, and return it.

Omit all the empty parenthesis pairs that do not affect the one-to-one mapping relationship between the string and the original binary tree.

Solution

DFS搜索，先序遍历到每个节点将其加入StringBuffer。
如果当前节点有左子节点或右子节点，则递归左子节点，并在前后添加一对括号。（如果有右子节点的情况即使左子节点为空也需要添加一对括号加以区别。）
如果当前节点有右子节点，则递归右子节点，并在前后添加一对括号。

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    StringBuffer sb;
    public String tree2str(TreeNode root) {
        sb = new StringBuffer();
        dfs(root);
        return sb.toString();
    }
    
    private void dfs(TreeNode root){
        if(root == null) return;
        sb.append(root.val);
        
        boolean hasLeft = root.left != null, hasRight = root.right != null;
        
        if(hasLeft || hasRight) sb.append("(");
        dfs(root.left);
        if(hasLeft || hasRight) sb.append(")");
        
        if(hasRight) sb.append("(");
        dfs(root.right);
        if(hasRight) sb.append(")");
    }
}

Posted 2022-09-06Updated 2022-09-06LeetCode / Medium3 minutes read (About 387 words)

814. Binary Tree Pruning

Question

Given the root of a binary tree, return the same tree where every subtree (of the given tree) not containing a 1 has been removed.

A subtree of a node node is node plus every node that is a descendant of node.

Solution 1

DFS搜索，首先递归两个子节点。
在搜索时如果节点为0且两个子节点均为null，则返回null。否则返回节点本身。

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode pruneTree(TreeNode root) {
        if(root == null) return null;
        root.left = pruneTree(root.left);
        root.right = pruneTree(root.right);
        if(root.left == null && root.right == null && root.val == 0) return null;
        else return root;
    }
}

Solution 2

DFS搜索，返回子节点和自己中是否包含1。
如果节点为null，则返回false。
如果自己为1，则返回true。
否则返回两个子节点中是否有true。

BFS搜索，根据每个节点的子节点是否包含1来决定左右子节点是否保存。
如果没有1，则将对应的子节点修改为null。

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode pruneTree(TreeNode root) {
        if(!hasOne(root)) return null;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()){
            TreeNode curr = q.poll();
            if(hasOne(curr.left)) q.add(curr.left);
            else curr.left = null;
            if(hasOne(curr.right)) q.add(curr.right);
            else curr.right = null;
        }
        return root;
    }
    
    private boolean hasOne(TreeNode root){
        if(root == null) return false;
        if(root.val == 1) return true;
        else return hasOne(root.left) || hasOne(root.right);
    }
}

Posted 2022-09-02Updated 2022-09-02LeetCode / Esaya minute read (About 209 words)

637. Average of Levels in Binary Tree

Question

Given the root of a binary tree, return the average value of the nodes on each level in the form of an array. Answers within 10<sup>-5</sup> of the actual answer will be accepted.

Solution

BFS搜索，记录单层的总和sum和单层的个数count。
每次遍历一个层级的所有节点，并更新sum和count。
遍历完毕后将当层级的平均数加入列表，同时将sum和count清零。

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Double> averageOfLevels(TreeNode root) {
        List<Double> res = new ArrayList<>();
        Queue<TreeNode> q = new LinkedList<>();
        
        double sum = 0, count = 0;
        int level = 1;
        q.add(root);
        
        while(!q.isEmpty()){
    
            for(int i = 0; i < level; i++){
                TreeNode curr = q.poll();
                if(curr.left != null) q.add(curr.left);
                if(curr.right != null) q.add(curr.right);
                count++;
                sum += curr.val;
            }
            res.add(sum/count);
            sum = 0;
            count = 0;
            level = q.size();
        }
        return res;
    }
}

Posted 2022-07-27Updated 2022-07-27LeetCode / Medium / 复习2 minutes read (About 343 words)

114. Flatten Binary Tree to Linked List

Question

Given the root of a binary tree, flatten the tree into a “linked list”:

The “linked list” should use the same TreeNode class where the right child pointer points to the next node in the list and the left child pointer is always null.

The “linked list” should be in the same order as a pre-order** traversal** of the binary tree.

Solution

全局变量prev，初始化为null，用来记录上一个访问的节点。

由于最后要达到先序遍历（根节点-左子节点-右子节点）的数据结构顺序，因此在进行访问时需要与先序遍历的操作相反，首先递归右子节点，然后递归左子节点，最后修改当前节点。

先遍历当前节点的右侧节点，再遍历当前节点的左侧节点。
最后处理当前节点，将左子节点设置为null，右子节点设置为prev。
最后将当前节点保存在prev上。

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    TreeNode prev = null;
    public void flatten(TreeNode root) {
        if(root == null) return;
        flatten(root.right);    //traverse right nodes first
        flatten(root.left); //traverse left nodes
        root.left = null;   //set current node's left child node to null
        root.right = prev;  //set current node's right child node to previous node
        prev = root;    //update previous node
    }
}

Posted 2022-06-18Updated 2022-06-17Hard / 复习10 minutes read (About 1452 words)

968. Binary Tree Cameras

Question

You are given the root of a binary tree. We install cameras on the tree nodes where each camera at a node can monitor its parent, itself, and its immediate children.

Return the minimum number of cameras needed to monitor all nodes of the tree.

Solution 1

贪心算法，后序遍历。每次递归根据下面两个子节点的状态来决定当前节点的状态。

每个节点一共有三种状态：

未被监控，返回0。
摄像头，返回1。
已被监控，返回2。

递归，当当前节点为空，则返回2，表示已被监控。这样叶子节点则为未被监控的状态。

如果下面的子节点有一个未被监控，则当前节点需要设置相机，返回1，计数res+1。
如果下面的子节点有一个为摄像头，则当前节点已被监控，返回2。
否则下面的节点均为已被监控，此时返回未被监控0。

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    int res = 0; //记录摄像头个数
    public int minCameraCover(TreeNode root) {
        if(judge(root) == 0) res++;  //如果根节点未被监控，则需要增加一个摄像机
        return res;
    }
    public int judge(TreeNode root){
        if(root == null) return 2;   //根节点为空时返回2，这样叶子节点变为未被监控
        int left = judge(root.left);
        int right = judge(root.right);

        if(left == 0 || right == 0){    //如果左右子节点有未被监控的节点，则当前节点设置为摄像机，结果加一，返回1
            res++;
            return 1;
        }
        if(left == 1 || right == 1) return 2;    //如果左右子节点中有摄像机，则当前节点已被监控，返回2
        return 0;   //如果左右子节点都被监控，则当前节点未被监控，返回0
    }
}

Solution 2

参考：从递归优化到树形DP

树形DP。
递归，每次返回当前节点所有子节点的最小相机数。
每一个节点有三种状态：

放置了相机。
没有相机，但是被父节点parent监控。
没有相机，但是被子节点son监控。

将三种状态分别传入minCam()方法。

递归方法 minCam()

在递归时传入两个参数hasCamera和isWatched，来判断当前节点是否有相机，是否被监控。
当当前节点为空节点时，如果设置应当有相机（做不到）则返回无限大，消除这个返回值。如果不应该有相机，则返回0。

向下递归子节点。

当当前节点应该有相机时：
子节点一定被监控因此isWatched为true。
子节点可以放置或不放置相机，因此hasCamera可以为true或false。
注意当前位置放置相机，则子节点最多放置一个相机，因此一共有三种组合。
由于相机至少有一个，因此返回其中的最小值+1。
当当前节点没有放置相机，但被父节点监控时：
左右节点一共有四种组合，分别同时将子节点的监控状态向下递归。
返回其中的最小值。
当当前节点没有放置相机，也没有被父节点监控，而是被子节点监控时：
子节点至少有一个相机，向下递归状态，一共有三种组合。
返回其中的最小值

然后分别调用minCam(root, true, true)和minCam(root, false, fasle)，取两者中的小值，即可得到答案。

树形dp优化剪枝

上面的方法实际采用时会超时，因为我们重复了三次调用一个子树下的三种状态的minCam。
因此我们可以将三种状态下的minCam分别保存在数组中返回。

withCam: 当前子树root有相机。
noCamWatchedByParent: 当前子树root没有相机，被父节点监控。
noCamWatchedBySon: 当前子树root没有相机，被子节点监控。

在每次递归时，获取数组minCam(root.left)和minCam(root.right)。
然后根据左右子节点的三个参数来计算当前节点的新的三个参数，将其返回。

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int minCameraCover(TreeNode root) {
        return Math.min(minCam(root, true, true), minCam(root, false, false));
    }
    
    private int minCam(TreeNode root, boolean hasCamera, boolean isWatched){
        if(root == null) return hasCamera ? Integer.MAX_VALUE / 2 : 0;

        if(hasCamera){
            int min = Math.min(minCam(root.left, false, true) + minCam(root.right, false, true), minCam(root.left, true, true) + minCam(root.right, false, true));
            min = Math.min(min, minCam(root.left, false, true) + minCam(root.right, true, true));
            return 1 + min;
        }
        else if(isWatched){
            int min = Math.min(minCam(root.left, true, true) + minCam(root.right, true, true), minCam(root.left, true, true) + minCam(root.right, false, false));
            min = Math.min(min, minCam(root.left, false, false) + minCam(root.right, true, true));
            min = Math.min(min, minCam(root.left, false, false) + minCam(root.right, false, false));
            return min;
        }
        else{
            int min = Math.min(minCam(root.left, true, true) + minCam(root.right, true, true), minCam(root.left, true, true) + minCam(root.right, false, false));
            min = Math.min(min, minCam(root.left, false, false) + minCam(root.right, true, true));
            return min;
        }
    }
}

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int minCameraCover(TreeNode root) {
        int[] res = minCam(root);
        return Math.min(res[0], res[2]);
    }
    
    private int[] minCam(TreeNode root){
        if(root == null){
            return new int[] {Integer.MAX_VALUE/2, 0, 0};
        }
        int[] left = minCam(root.left);
        int[] right = minCam(root.right);

        int withCam = 1 + Math.min(left[1] + right[1], Math.min(left[0] + right[1], left[1] + right[0]) );
        int noCamWatchedByParent = Math.min( left[0] + right[0], Math.min( left[0] + right[2], Math.min( left[2] + right[0], left[2] + right[2] )));
        int noCamWatchedBySon = Math.min( left[0] + right[0], Math.min( left[0] + right[2], left[2] + right[0]));
        return new int[] {withCam, noCamWatchedByParent, noCamWatchedBySon};
    }
}

Posted 2022-05-18Updated 2022-05-17LeetCode / Medium2 minutes read (About 234 words)

1379. Find a Node of a Binary Tree in a Clone Tree

Question

Given two binary trees original and cloned and given a reference to a node target in the original tree.

The cloned tree is a copy of the original tree.

Return a reference to the same node in the cloned tree.

Note that you are not allowed to change any of the two trees or the target node and the answer must be a reference to a node in the cloned tree.

Solution

DFS搜索，同步递归original和cloned的子节点。
当在original里找到target的时候返回当前的cloned节点。

注意可以先判断一个分支中的返回值是否为空，如果不为空则直接返回。反之则返回另一个分支。这样操作可以进行一部分剪枝。

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */

class Solution {
    public final TreeNode getTargetCopy(final TreeNode original, final TreeNode cloned, final TreeNode target) {
        if(original == null) return null;
        if(original.equals(target)) return cloned;
        
        TreeNode left = getTargetCopy(original.left, cloned.left, target);
        if(left != null) return left;
        else return getTargetCopy(original.right, cloned.right, target);
    }
}

Posted 2022-05-15Updated 2022-05-14LeetCode / Mediuma minute read (About 153 words)

1302. Deepest Leaves Sum

Question

Given the root of a binary tree, return the sum of values of its deepest leaves.

Solution

BFS搜索，层序遍历，每次计算每个层级的总和。
最后返回最后一个层级总和。

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int deepestLeavesSum(TreeNode root) {
        Deque<TreeNode> q = new LinkedList<>();
        int res = 0;
        
        q.offer(root);
        
        int level = q.size();
        
        while(!q.isEmpty()){
            int sum = 0;
            for(int i = 0; i < level; i++){
                TreeNode curr = q.poll();
                sum += curr.val;
                if(curr.left != null) q.offer(curr.left);
                if(curr.right != null) q.offer(curr.right);
            }
            res = sum;
            level = q.size();
        }
        return res;
    }
}

Posted 2022-05-05Updated 2022-05-04LeetCode / Hard4 minutes read (About 589 words)

297. Serialize and Deserialize Binary Tree

Question

Serialization is the process of converting a data structure or object into a sequence of bits so that it can be stored in a file or memory buffer, or transmitted across a network connection link to be reconstructed later in the same or another computer environment.

Design an algorithm to serialize and deserialize a binary tree. There is no restriction on how your serialization/deserialization algorithm should work. You just need to ensure that a binary tree can be serialized to a string and this string can be deserialized to the original tree structure.

Clarification: The input/output format is the same as how LeetCode serializes a binary tree. You do not necessarily need to follow this format, so please be creative and come up with different approaches yourself.

Solution

编码过程

编码时采用BFS搜索，将二叉树按层级组成字符串。
当当前节点不等于null时，添加当前节点的值和一个符号。
然后将其左右子节点加入队列。
当当前节点为null时，添加一个非数字字符和一个符号。

解码过程

解码时同样采用BFS搜索，按层级恢复二叉树。
首先将字符串根据符号进行分割，变为字符串数组。
如果第一个字符表示为null，返回null。

否则将第一个数字组成根节点并加入队列。创建一个指针i记录位置。
当队列不为空，且指针i未越界时，根据指针i上的字符串创建当前节点的左子节点。
将指针右移，如果没有越界则创建当前节点的右子节点，然后将指针右移。

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder data = new StringBuilder();
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        while(!q.isEmpty()){
            TreeNode curr = q.poll();
            if(curr == null) data.append("n,");
            else {
                data.append(curr.val + ",");
                q.add(curr.left);
                q.add(curr.right);
            }
        }
        return data.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] values = data.split(",");
        if(values[0].equals("n")) return null;
        TreeNode root = new TreeNode(Integer.parseInt(values[0]));
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        int i = 1;     
        while(!q.isEmpty() && i < values.length){
            TreeNode curr = q.poll();
            curr.left = values[i].equals("n") ? null : new TreeNode(Integer.parseInt(values[i]));
            if(i++ < values.length) curr.right = values[i].equals("n") ? null : new TreeNode(Integer.parseInt(values[i]));
            if(curr.left != null) q.add(curr.left);
            if(curr.right != null) q.add(curr.right);
            i++;
        }
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec ser = new Codec();
// Codec deser = new Codec();
// TreeNode ans = deser.deserialize(ser.serialize(root));

Posted 2022-05-03Updated 2022-07-26LeetCode / Medium2 minutes read (About 337 words)

236. Lowest Common Ancestor of a Binary Tree

Question

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”

Solution

DFS搜索，后序遍历。
当当前节点是p或者q，返回节点自身，代表已经找到节点。（如两个节点最终只访问了一个，说明那一个节点本身就是LCA。）

分别递归搜索左右子节点。

如果左子节点为空，则返回右子节点，反之亦然，保证找到的节点可以被返回。
如果左右子节点均不等于null，则当前节点是最低公共祖先（LCA），返回当前节点。

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        
        if(root == null) return null;
        if(root == p) return p; //found target and return
        if(root == q) return q; //found target and return
        
        TreeNode left = lowestCommonAncestor(root.left, p, q);  //search left branch
        TreeNode right = lowestCommonAncestor(root.right, p, q);    //search right branch
           
        if(left == null) return right;  //if left not found target, return the right branch
        else if(right == null) return left; //if right not found target, return the left branch
        else return root;   //if both found target, return the root
    }
}

Posted 2022-05-03Updated 2022-05-02LeetCode / Medium / 复习5 minutes read (About 767 words)

105. Construct Binary Tree from Preorder and Inorder Traversal

Given two integer arrays preorder and inorder where preorder is the preorder traversal of a binary tree and inorder is the inorder traversal of the same tree, construct and return the binary tree.

先序遍历时，访问的顺序是[根节点 - 左子节点 - 右子节点]。
中序遍历时，访问的顺序是[左子节点 - 根节点 - 右子节点]。
可以注意到根节点与左子节点的顺序是相反的，因此我们可以利用栈将节点储存起来，当挤出时顺序自然是调转的。

按照先序遍历来创建树，遍历先序数组。同时将指针指向中序遍历的数组的头部。
先创建根节点，并将其放入栈中。分为两种情况讨论。

情况一，处理当前根节点的左子节点，并将其入栈：

当栈顶的节点值与中序遍历当前的节点值不同时，说明当前的根节点仍有左子节点。

先序：[根节点 - 左子节点 - 右子节点]
中序：[左子节点 - 根节点 - 右子节点]

此时将栈顶的节点的左子节点设置为先序数组对应的节点，继续遍历下一个先序数组。

栈内：[根节点 - 左子节点]
先序：[根节点 - 左子节点 - 右子节点]
中序：[左子节点 - 根节点 - 右子节点]

情况二，寻找栈内节点们的右子节点：

当栈顶的节点与中序遍历当前的节点值相同时，说明我们经过了当前根节点的先序遍历中的最后一个左子节点。
当前先序数组指针指向了当前栈内节点一个右子节点。

栈内：[根节点 - 左子节点]
先序：[根节点 - 左子节点 - 右子节点]
中序：[左子节点 - 根节点 - 右子节点]

此时我们开始向右移动中序遍历的指针，寻找先序遍历指针中的节点应该是当前栈内哪一个节点的右子节点。
此时栈内节点的顺序，与中序遍历的左子节点顺序正好相反。当栈顶与中序遍历的指针相等时，挤出栈顶并将中序指针右移，直到两者不相等或栈空。
此时将最后挤出的根节点的右子节点设置为当前先序数组对应的节点，继续遍历下一个先序数组。

当遍历完成后，返回根节点即可。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int j = 0;
        Stack<TreeNode> stack = new Stack<>();
        TreeNode root = new TreeNode(preorder[0]);
        stack.add(root);
        
        for(int i = 1; i < preorder.length; i++){
            TreeNode curr = new TreeNode(preorder[i]);
            TreeNode prev = stack.peek();
            if(inorder[j] != prev.val){
                prev.left = curr;
                stack.add(curr);
            }
            else{
                while(!stack.isEmpty() && inorder[j] == stack.peek().val){
                    prev = stack.pop();
                    j++;
                }
                prev.right = curr;
                stack.add(curr);
            }
        }
        return root;
    }
}

Posted 2022-05-02Updated 2022-05-01LeetCode / Mediuma minute read (About 173 words)

199. Binary Tree Right Side View

Given the root of a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

BFS搜索。层级遍历各个节点，当节点为该层级最后一个节点时，将其值加入返回列表。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> ret = new ArrayList<>();
        if(root == null) return ret;
        Queue<TreeNode> q = new LinkedList<>();
        q.add(root);
        int size = 1;
        while(!q.isEmpty()){
            for(int i = 0; i < size; i++){
                TreeNode curr = q.poll();
                if(i == size - 1) ret.add(curr.val);
                if(curr.left != null) q.add(curr.left);
                if(curr.right != null) q.add(curr.right);
            }
            size = q.size();
        }
        return ret;
    }
}

Posted 2022-05-02Updated 2022-05-01LeetCode / Medium2 minutes read (About 294 words)

113. Path Sum II

Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum. Each path should be returned as a list of the node values, not node references.

A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children.

回溯，每次将root的值添加到list中。并计算新的sum值。分别向左右子节点进行递归，然后回溯。
当节点没有左右子节点，且sum等于targetSum则将新建的list添加到结果中。
（注意这一步内也需要进行回溯操作。）

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<List<Integer>> ret;
    int target;
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        ret = new ArrayList<>();
        if(root == null) return ret;
        target = targetSum;
        backTrack(root, 0, new ArrayList<>());
        return ret;
    }
    
    private void backTrack(TreeNode root, int sum, List<Integer> nodes){
        if(root.left == null && root.right == null){
            sum += root.val;
            if(sum == target){
                nodes.add(root.val);
                ret.add(new ArrayList<Integer>(nodes));
                nodes.remove(nodes.size()-1);
            }
            return;
        }
        nodes.add(root.val);
        sum += root.val;
        if(root.left != null) backTrack(root.left, sum, nodes);
        if(root.right != null) backTrack(root.right, sum, nodes);
        nodes.remove(nodes.size()-1);
        sum -= root.val;
    }
}

Posted 2022-05-02Updated 2022-05-01LeetCode / Easy / 复习2 minutes read (About 237 words)

108. Convert Sorted Array to Binary Search Tree

Given an integer array nums where the elements are sorted in ascending order, convert it to a height-balanced binary search tree.

A height-balanced binary tree is a binary tree in which the depth of the two subtrees of every node never differs by more than one.

以中序遍历的顺序创建节点（代码实现时先序遍历），每次选择范围的中间值mid为根节点。
根节点的左子节点递归左侧left直到mid-1的位置。
根节点的右子节点递归mid+1直到右侧right的位置。
当left > right时，返回null作为二叉树的叶子节点。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public TreeNode sortedArrayToBST(int[] nums) {
        return build(nums, 0, nums.length-1);
    }
    
    private TreeNode build(int[] nums, int left, int right){
        if(left > right) return null;
        
        int mid = left + (right - left) / 2;
        TreeNode root = new TreeNode(nums[mid]);
        root.left = build(nums, left, mid-1);
        root.right = build(nums, mid+1, right);
        
        return root;
    }
}

Posted 2022-04-21Updated 2022-05-12LeetCode / Mediuma minute read (About 213 words)

117. Populating Next Pointers in Each Node II

Question

Given a binary tree
1
2
3
4
5
6
struct Node {
 int val;
 Node *left;
 Node *right;
 Node *next;
}
Populate each next pointer to point to its next right node. If > there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Solution

BFS搜索，从右至左将每层节点放入队列。
用一个size记录该层级放入节点的数量，每次循环将size-1，当size归零时放入新一层级的节点。

Code

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}
    
    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, Node _left, Node _right, Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
};
*/

class Solution {
    public Node connect(Node root) {
        if(root == null) return root;
        
        Queue<Node> q = new LinkedList();
        q.add(root);
        
        while(!q.isEmpty()){
            int size = q.size();
            Node next = null;
            while(size > 0){
                size--;
                Node curr = q.poll();
                curr.next = next;
                next = curr;
                if(curr.right != null) q.add(curr.right);
                if(curr.left != null) q.add(curr.left);
            }
        }
        return root;
    }
}

Question

Solution

Code

Question

Solution

Code

Question

Solution 1

Code

Solution 2

Code

Question

Solution

Code

Question

Solution

Code

Question

Solution 1

Code

Solution 2

递归方法 minCam()

树形dp优化剪枝

Code

Code

Question

Solution

Code

Question

Solution

Code

Question

Solution

编码过程

解码过程

Code

Question

Solution

Code

Question

Solution

Code

Recents

Archives

Links